package com.cg.leetcode;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * 3.无重复字符的最长子串
 *
 * @program: LeetCode->LeetCode_3
 * @author: cg
 * @create: 2022-04-16 17:23
 **/
public class LeetCode_3 {

    @Test
    public void test3() {
        System.out.println(lengthOfLongestSubstring("abcabcbb"));
    }

    /**
     * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
     * <p>
     * 示例 1:
     * 输入: s = "abcabcbb"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
     * <p>
     * 示例 2:
     * 输入: s = "bbbbb"
     * 输出: 1
     * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
     * <p>
     * 示例 3:
     * 输入: s = "pwwkew"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
     *  
     * 提示：
     * 0 <= s.length <= 5 * 104
     * s 由英文字母、数字、符号和空格组成
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0, max = 0;
        while (right < s.length()) {
            char ch = s.charAt(right);
            right++;
            window.put(ch, window.getOrDefault(ch, 0) + 1);
            // 该字符有重复，从左边开始删，直到该字符没有重复
            while (window.get(ch) > 1) {
                char c = s.charAt(left);
                left++;
                window.put(c, window.get(c) - 1);
            }
            max = Math.max(max, right - left);
        }
        return max;
    }

}
